package q790_numTilings;

public class Solution_2 {
    private static final long MOD = (long) 1e9 + 7;
    /*
    更加简单的找规律方法
    https://leetcode.cn/problems/domino-and-tromino-tiling/solution/by-endlesscheng-umpp/
     */
    public int numTilings(int n) {
        if (n == 1) return 1;
        long a = 1, b = 1, c = 2;
        for (int i = 3; i <= n; ++i) {
            long f = (c * 2 + a) % MOD;
            a = b;
            b = c;
            c = f;
        }
        return (int) c;
    }
}
